//*************************************************
//Program #4       LFU.cpp
//*************************************************
//Names: Stephen Durfrey,  Andrew Brock
//Due: April 23, 2010
//Operating Systems
//Related Files:  LFU.h
// Least-Frequently-Used PGA: the page with the smallest count 
//  be replaced.

#include "LFU.h"
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>

using namespace std;

//Default Constructor
LFU::LFU()
{
}

//*************************************************
//LFU::init - initializes the varibles based on the variables
// passed into the program.
//*************************************************
void LFU::init(int frames, vector<int> ref_str)
{
	num_frames = frames;
	ref_string = ref_str;
	num_faults = 0;
	ref_page = ref_string.begin();
}
//*************************************************
//LFU::checkFrame - checks to see if the value "check"
// is in the frames.  If it is its location is passed back
// otherwise check == frames.end()
//*************************************************
vector<int>::iterator LFU::checkFrame(vector<int>::iterator check)
{
	bool found = false;
	vector<int>::iterator value, begin, end;

	value = end = frames.end();

	for(begin = frames.begin(); begin != end && !found; begin++)
	{
		if(*begin == *check)
		{
			value = begin;
			found = true;
		}
	}

	return value;

}
//*************************************************
// LFU::findFrame - finds the lease frequently used frame
// and returns its position.
//*************************************************
vector<int>::iterator LFU::findFrame()
{
	vector<int>::iterator beginFrame, beginLFU, minLFU, minFrames;

	minFrames = frames.begin();
	minLFU = times_used.begin();
	beginLFU = times_used.begin();

	for(beginFrame = frames.begin(); beginFrame != frames.end(); beginFrame++, beginLFU++)
	{
		if(*beginLFU < *minLFU)
		{
			minLFU = beginLFU;
			minFrames = beginFrame;
		}
	}

	*minLFU = 1;

	return minFrames;
}
//*************************************************
//LFU::removePage() - this is where the loop is that the LFU
// page replacement algorithm is tested.
//*************************************************
void LFU::removePage()
{
	vector<int>::iterator begin, end, pos, foundPos, position;
	end = ref_string.end();
	ref_page = ref_string.begin();

	do
	{//BEGIN DO-WHILE
		if(frames.size() != num_frames)
		{//BEGIN IF
			//First checks to see if *ref_page is already in frames.
			position = checkFrame(ref_page);
			if(position == frames.end())
			{//Frames has an empty slot
				frames.push_back(*ref_page);
				num_faults++;
				times_used.push_back(1);
			}
		}//END IF
		else
		{//BEGIN ELSE
			begin = frames.begin();
			ref_used = times_used.begin();
			
			//check to see if the ref_page currently exists in the set of frames
			pos = find(frames.begin(), frames.end(), *ref_page);

			//if it doesn't exist in frames
			if(pos == frames.end())
			{
				foundPos = findFrame();

				*foundPos = *ref_page;
				num_faults++;

			}
			else 
			{
				//Increments the value stored in times_used
				*pos++;
			}

		}//END ELSE
		ref_page++;
	}while(ref_page != ref_string.end());//END DO-WHILE




}
//*************************************************
//LSU::run - executes the algorithm and then outputs
// the results of values num_frames and num_faults
//*************************************************
void LFU::run()
{
	char value[50];
	string value_param;

	removePage();

	sprintf(value, "%d , %d", num_frames, num_faults);

	value_param = (string)value;
	addCsvString("LFU.txt", value_param );
}


